As per the document about std::lower_bound, which says that:
The range [first, last) must be partitioned with respect to the expression element < value or comp(element, value), i.e., all elements for which the expression is true must precede all elements for which the expression is false. A fully-sorted range meets this criterion.
I have a little difficulty to fully understand it.
1.What's element < value? It seems that element (or value) is never mentioned before this paragraph in the aforementioned document. Does the said element mean the elements before the current element, and the said value means the value of the current element?
UPDATED:
2.Since whether a specific sequence is valid(i.e. suits the requirement) or not depends the value, the requirement for a specific sequence could not be always be guaranteed when the value is different. I think it's meaningless to define such a requirement. It's seems that a fully sorted seuqence is more reliable and practical.
Sam Varshavchik :
\nWhat's element < value\n\nvalue is the parameter to lower_bound, see at the beginning of that page:\n\ntemplate< class ForwardIt, class T > ForwardIt lower_bound( ForwardIt\nfirst, ForwardIt last, const T& value );\n\nThe value in question is mentioned right here, the last parameter to the template. And element, references to some element and every element in the sequence.\nThis is rather a terse way to define the following: take every element in the sequence, one element at a time. When you do that, all elements for which the expression element < value returns true must appear in the sequence before all other elements, for which the same expression is false. It is explicitly intentional for the requirements to be defined in this manner, here's the explanation:\nFor example, if value is 4, and we're talking about natural integers, here's one such sequence:\n1, 2, 3, 4, 5, 6\n\nHere, all the elements for which this expression is true (1, 2, and 3), appear before all the elements for which this expression is false (4, 5, and 6).\nThe following sequence is also a valid sequence, in this case:\n3, 2, 1, 6, 5, 4\n\nHere, same thing: 3, 2, and 1, for which the expression element < 4 is true, appears before value 4, 5 and 6 for which the expression element < 4 would be false. So, yes, this would also be a valid sequence for a call to lower_bound for the value of 4.\nThe following sequence will NOT be a valid sequence for this specific case of using std::lower_bound:\n1, 2, 4, 3, 5, 6\n\nAnd as far as why is this lower_bound requirement specified in such an strange manner, well, that would be a different question. But this is what it means.",
2022-02-09T02:01:53
rturrado :
From cppreference\n\nReturns an iterator pointing to the first element in the range [first,\nlast) that is not less than (i.e. greater or equal to) value, or last\nif no such element is found.\nThe range [first, last) must be partitioned with respect to the\nexpression element < value or comp(element, value), i.e., all elements\nfor which the expression is true must precede all elements for which\nthe expression is false. A fully-sorted range meets this criterion.\n\nFrom your question:\n\nWhat's element < value? It seems that element (or value) is never\nmentioned before this paragraph in the aforementioned document. Does\nthe said element mean the elements before the current element, and the\nsaid value means the value of the current element?\n\nvalue and comp are mentioned in the function signatures at the beginning of the page. value is the argument with which you call std::lower_bound, and comp an optional comparison function; shouldn't a comparison function be provided, < would be used instead.\nelement refers to each element in the range [first, last).\nSo, what std::lower_bound does is to compare value to the elements in the range until it finds the first one that is not "less than" (through < or comp) value.\nThe requirement for std::lower_bound to work is that the input range is partitioned in such a way that all the elements that are "less than" value are placed before the rest; that requirement is met, for example, if the range is fully sorted.\n(As @Passerby mentions in the comments below, std::lower_bound won't need to compare against all the elements that are "less than" value, due to the partitioned range requirement, but that is an implementation detail.)",
2022-02-09T01:58:18